/*
*/

#include "common.h"



struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    if (list1 == NULL)
        return list2;
    if (list2 == NULL)
        return list1;
    
    struct ListNode*  head, *cur;
    if (list1->val <= list2->val){
        head = list1;
        cur = head;
        list1 = list1->next;
    }
    else {
        head = list2;
        cur = head;
        list2 = list2->next;
    }

    while(list1 && list2){
        if (list1->val <= list2->val){
            cur->next = list1;
            cur = list1;
            list1 = list1->next;
        }
        else  {
            cur->next = list2;
            cur = list2;
            list2 = list2->next;
        }
    }

    cur->next = list2 == NULL ? list1 : list2;

    return head;
}



// struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
//     struct ListNode temp;
//     struct ListNode *head = &temp;
//     struct ListNode *cur = head;

//     while(list1 && list2){
//         if (list1->val <= list2->val){
//             cur->next = list1;
//             cur = list1;
//             list1 = list1->next;
//         }
//         else  {
//             cur->next = list2;
//             cur = list2;
//             list2 = list2->next;
//         }
//     }
    
//     cur->next = list2 == NULL ? list1 : list2;

//     return head->next;
// }



// struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
//     if (list1 == NULL) {
//         return list2;
//     } else if (list2 == NULL) {
//         return list1;
//     } else if (list1->val < list2->val) {
//         list1->next = mergeTwoLists(list1->next, list2);
//         return list1;
//     } else {
//         list2->next = mergeTwoLists(list1, list2->next);
//         return list2;
//     }
// }